package findDuplicateSubtrees

import (
	"strconv"
	"strings"
)

/*
寻找重复的子树
给定一棵二叉树 root，返回所有重复的子树。

对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。

如果两棵树具有相同的结构和相同的结点值，则它们是重复的。

*/
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// 当位于当前结点时，需要做两件事
// 1、知道自己的子树结构   （后序遍历解决）
// 2、需要知道是否存在跟自己一样的树结构 （map存已经遍历过的结点的树结构）（树结构序列化为字符串存储）
func findDuplicateSubtrees(root *TreeNode) []*TreeNode {
	//记录结果
	ans := make([]*TreeNode, 0)
	if root == nil {
		return ans
	}
	//记录以某个结点为根结点的子树情况
	m := make(map[string]int)
	builder := strings.Builder{}
	var find func(node *TreeNode) string

	find = func(node *TreeNode) string {
		if node == nil {
			// 空结点以 #表示
			return "#"
		}

		leftString := find(node.Left)
		rightString := find(node.Right)
		// 后序遍历位置，做拼接结点的操作
		builder.WriteString(leftString)
		builder.WriteString(",")
		builder.WriteString(rightString)
		builder.WriteString(",")
		builder.WriteString(strconv.Itoa(node.Val))
		curString := builder.String()
		// 存在相同的树结构吗？
		num := m[curString]
		if num == 1 {
			ans = append(ans, node)
		}
		m[curString]++
		builder.Reset()
		return curString
	}

	find(root)
	return ans
}
